package problems;

import java.math.BigInteger;

import utils.Utils;

public class Problem254 {
	private static final int[] factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
	
	public static void main(String[] args) {
		System.out.println(sumSg(20));
		System.out.println(sumSg(150));
	}

	private static int sumSg(int n) {
		long startTime = System.currentTimeMillis();
		
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			Utils.printProgress(i, n, startTime);
			sum += Utils.sumOfDigits(g(i)); // sg(i)
		}
		return sum;
	}

	private static int f(BigInteger n) {
		int sum = 0;
		String value = n.toString();
		for (int i = 0; i < value.length(); i++) {
			sum += factorials[value.charAt(i) - 48];
		}
		return sum;
	}

	private static BigInteger g(int i) {
		BigInteger increment = BigInteger.valueOf(i > 20 ? 10 : 1);
		BigInteger n = BigInteger.valueOf(i > 20 ? 9 : 1);
		while (true) {
			if (i == Utils.sumOfDigits(f(n))) { // sf(n)
				System.out.printf("g(%d) = %d%n", i, n);
				return n;
			}
			n = n.add(increment);
		}
//		throw new IllegalStateException("Overflow! i=" + i);
	}
}
